# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
root=TreeNode(5,None,None)
root.left=TreeNode(4,None,None)
root.left.left=TreeNode(11,None,None)
root.left.left.left=TreeNode(7,None,None)
root.left.left.right=TreeNode(2,None,None)
root.right=TreeNode(8,None,None)
root.right.left=TreeNode(13,None,None)
root.right.right=TreeNode(4,None,None)
root.right.right.left=TreeNode(5,None,None)
root.right.right.right=TreeNode(1,None,None)

def dfs(root,targetSum,curSum,res,path):
    #出口条件
    if root.left==None and root.right==None:
        if curSum+root.val==targetSum:
            path.append(root.val)
            res.append(path[:])
            path.pop()
        return None
    if root.left!=None:
        path.append(root.val)
        dfs(root.left,targetSum,curSum+root.val,res,path)
        path.pop()
    if root.right!=None:
        path.append(root.val)
        dfs(root.right,targetSum,curSum+root.val,res,path)
        path.pop()

def pathSum(root, targetSum):
    res=[]
    path=[]
    dfs(root,targetSum,0,res,path)

    print(res)
pathSum(root,targetSum=22)